
//2.明码  九的九次方是多少 387,420,489
//#include <bits/stdc++.h>
//using namespace std;
//int a[10][32];
//int d[8];
//void Print(int n)
//{
//	memset(d,0,sizeof(d));
//	int i=0;
//	while(n)
//	{
//		d[i++]=abs(n%2);
//
//		n/=2;
//	}
//
//	for(int i=7;i>=0;i--)cout<<d[i];
//}
//int main()
//{
//	ios::sync_with_stdio(false);
//	for(int i=0;i<10;i++)
//	{
//		for(int j=0;j<32;j++)cin>>a[i][j];
//	}
//
//
//	int cnt=1;
//	for(int i=0;i<10;i++)
//	{
//		for(int j=0;j<32;j++)
//		{
//			Print(a[i][j]);
//			if(cnt%2==0)cout<<endl;
//			cnt++;
//		}
//	}
//	return 0;
//}

////3.乘积尾零 31
//#include <bits/stdc++.h>
//using namespace std;
//
//int num[10 * 10] = { 5650, 4542, 3554, 473, 946, 4114, 3871, 9073, 90, 4329,
//		2758, 7949, 6113, 5659, 5245, 7432, 3051, 4434, 6704, 3594,
//		9937, 1173, 6866, 3397, 4759, 7557, 3070, 2287, 1453, 9899,
//		1486, 5722, 3135, 1170, 4014, 5510, 5120, 729, 2880, 9019,
//		2049, 698, 4582, 4346, 4427, 646, 9742, 7340, 1230, 7683,
//		5693, 7015, 6887, 7381, 4172, 4341, 2909, 2027, 7355, 5649,
//		6701, 6645, 1671, 5978, 2704, 9926, 295, 3125, 3878, 6785,
//		2066, 4247, 4800, 1578, 6652, 4616, 1113, 6205, 3264, 2915,
//		3966, 5291, 2904, 1285, 2193, 1428, 2265, 8730, 9436, 7074,
//		689, 5510, 8243, 6114, 337, 4096, 8199, 7313, 3685, 211 };
//
//
//int cnt_2=0,cnt_5=0;
//void getcnt2(int n)
//{
//	while(n%2==0)
//	{
//		cnt_2++;
//		n/=2;
//	}
//}
//void getcnt5(int n)
//{
//	while(n%5==0)
//	{
//		cnt_5++;
//		n/=5;
//	}
//}
//int main()
//{
//
//	for(int i=0;i<100;i++)
//	{
//		getcnt2(num[i]);
//		getcnt5(num[i]);
//	}
//	cout<<min(cnt_2,cnt_5);
//	return 0;
//}



////4.测试次数
//#include <bits/stdc++.h>
//using namespace std;
//int
//int main()
//{
//
//}


////5.快速排序  quick_select(a,i,r,k-(i-l));
//#include <stdio.h>
//#include <bits/stdc++.h>
//using namespace std;
//int quick_select(int a[], int l, int r, int k) {
//	int p = rand() % (r - l + 1) + l;
//	int x = a[p];
//
//	{
//	int t = a[p];
//	a[p] = a[r];//将最右的先换到随机数位置，基准值在最右边，最右边的在随机数位置
//	a[r] = t;
//	}
//
//	int i = l, j = r;
//	//i从左向右找大
//	//j从右向左找小
//	while(i < j) {
//		while(i < j && a[i] < x) i++;
//		if(i < j) {
//			a[j] = a[i];
//			j--;
//		}
//		while(i < j && a[j] > x) j--;
//		if(i < j) {
//			a[i] = a[j];
//			i++;
//		}
//	}
//	a[i] = x;
//	p = i;
//	if(i - l + 1 == k) return a[i];
////	if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
//	if(i - l + 1 < k) return quick_select(a,i,r,k-(i-l));
//	else return quick_select(a, l, i - 1, k);
//}
//
//int main()
//{
//	int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};//1 2 4 5 7 8 12
//	printf("%d\n", quick_select(a, 0, 14, 7));
////	cout<<sizeof(a)/sizeof(int);
//	return 0;
//}


////6.递增三元组 %71
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e5+10;
//int a[N],b[N],c[N];
//int main()
//{
//	ios::sync_with_stdio(false);
//	int n;
//	cin>>n;
//	for(int i=1;i<=n;i++)
//	{
//		cin>>a[i];
//	}
//		for(int i=1;i<=n;i++)
//	{
//		cin>>b[i];
//	}
//		for(int i=1;i<=n;i++)
//	{
//		cin>>c[i];
//	}
//	sort(a,a+n);
//	sort(b,b+n);
//	sort(c,c+n);
//
//	int cnt=0;
//	for(int i=1;i<=n;i++)
//	{
//		int j=1;
//		while(a[i]>=b[j])j++;
//		for(;j<=n;j++)
//		{
//			int k=1;
//			while(b[j]>=c[k])k++;
//  			for(;k<=n;k++)
//			{
//				if(a[i]<b[j]&&b[j]<c[k])cnt++;
//			}
//		}
//
//	}
//
//
//	return 0;
//}



////7.螺旋折线 31%
//#include <bits/stdc++.h>
//using namespace std;
//const int N= 1e3;
//const int M=1e2;
//int dp[N][N];
//int main()
//{
//    ios::sync_with_stdio(false);
//     int x,y;
//     cin>>x>>y;
//     int flag=0;
//     int n=100;//转二十圈
//     int w=1,h=1;
//     int a=0,b=0;
//     dp[M+a][M+b]=0;
//     while(n--)
//     {
//       if(flag%4==0)//向左
//          {
//              for(int i=1;i<=w;i++)
//              {
//        		  b--;
//                  dp[M+a][M+b]=dp[M+a][M+b+1]+1;
////                  cout<<dp[M+a][M+b]<<' ';
//              }
//              flag++;
//              w++;
//          }
//
//          if(flag%4==1)//向上
//          {
//              for(int i=1;i<=h;i++)
//              {
//                  a--;
//                  dp[M+a][M+b]=dp[M+a+1][M+b]+1;
////				  cout<<dp[M+a][M+b]<<' ';
//			  }
//              flag++;
//              h++;
//          }
//
//          if(flag%4==2)//向右
//          {
//              for(int i=1;i<=w;i++)
//              {
//                  b++;
//                  dp[M+a][M+b]=dp[M+a][M+b-1]+1;
////                  cout<<dp[M+a][M+b]<<' ';
//              }
//              flag++;
//              w++;
//          }
//          if(flag%4==3)//向下
//          {
//              for(int i=1;i<=h;i++)
//              {
//                  a++;
//                  dp[M+a][M+b]=dp[M+a-1][M+b]+1;
////                  cout<<dp[M+a][M+b]<<' ';
//              }
//              flag++;
//              h++;
//          }
//     }
//
//     cout<<dp[M-y][M+x]<<endl;
//    return 0;
//}


////8.日志统计
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	return 0;
//}